1. Field of the Invention
The present invention relates to a scheme for generating test patterns for logic circuits specifying primary input logic values for examining logic circuits.
2. Description of the Background Art
The conventionally widely used test pattern generation method is for detecting the so called stuck fault in which a logic value of a signal line within a circuit is going to be fixed to 0 or 1. In order to detect such a stuck fault, there is a need to derive the primary input logic values such that the primary output logic values differ for a case of the presence of the fault and a case of the absence of the fault.
In order to derive such primary input logic values, it is necessary to set up the logic value opposite to that in a case of the fault with respect to the signal line with the fault in such a manner that the change of the signal values can be propagated through at least one path from the signal line with the fault to the primary output. In other words, the generation of the test patterns is effectively the problem of controlling the primary inputs such that the signal lines within the circuit and their logic values can be set appropriately according to the target fault.
The representative conventional test pattern generation methods includes the following:
[Ref. 1] U.S. Pat. No. 4,204,633 (May 27, 1980) PA1 [Ref. 2] P. Goel, "An implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE Trans. on Computers, Vol. C-20, No. 3, pp. 215-222, March, 1981; PA1 [Ref. 3] H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms", IEEE Trans. on Computers, Vol. C-32, No. 12, pp. 1137-1144, December, 1983.
In the following, the conventional test pattern generation method will be explained according to the teaching disclosed in [Ref. 1].
FIG. 1 shows a schematic configuration of a test pattern generation system for realizing the conventional Test pattern generation method. In this conventional test pattern generation system of FIG. 1, an object generation unit 10 generates an object, i.e., a set of a signal line and a logic value to be set to that signal line, which is required in generating the test pattern for each fault.
Then, a backtrace operation unit 8 propagates the generated object to the input side by carrying out the backtrace operation in which the new object is generated at the input side of each logic gate to which the generated object has propagated according to the function of that logic gate, so as to satisfy the generated object.
A decision making unit 9 judges whether the object has reached to the primary input or not. In a case the object has not reached the primary input, the operation returns to the object generation unit 10 which generates another object. On the other hand, in a case the object has reached the primary input, the decision making unit 9 decides the assignment of the logic value at the primary input.
Then, a conflict determination unit 11 determines whether the incorrect decision has been made by the decision making unit 9 or not. In a case the incorrect decision has been made, a backtracking unit 12 carries out the operation called backtracking in which the decision making is carried out anew.
Finally, a test pattern judgement unit 13 judges whether the test pattern has been obtained or not by checking whether there is a difference in the primary output logic value for the normal circuit and the circuit with fault. If it is judged that the test pattern has been obtained, the logic value assigned to the primary input is outputted as the appropriate test pattern, whereas otherwise the operation returns to the object generation unit 10 to repeat the above process for the next object.
More specifically, the operation to obtain the primary input logic value from the object in this conventional system proceeds according to the flow chart of FIG. 2 as follows.
Namely, whether the object is the primary input or not is determined at the step 21. In a case the signal line of the object is the primary input, the logic value is going to be assigned to the primary input according to the level of that object at the step 22. On the other hand, in a case the signal line of the object is not the primary input, the type of the logic gate which is driving the signal line and the level of the current object are determined at the step 23.
Then, a new object is generated with respect to the input of the logic gate according to the determined type of the logic gate and level of the current object as follows.
First, in a case the driving logic gate is OR/NAND and the level is 0, or the driving logic gate is AND/NOR and the level is 1, next at the step 24, the signal line of a new object to be generated is set to be one input signal line of the driving logic gate which is hardest to control from the primary input among those input signal lines having the variable values. On the other hand, in a case the driving logic gate is OR/NAND and the level is 1, or the driving logic gate is AND/NOR and the level is 0, next at the step 25, the signal line of a new object to be generated is set to be one input signal line of the driving logic gate which is easiest to control from the primary input among those input signal lines having the variable values.
Next, the type of the driving logic gate is determined at the step 26. Then, when the driving logic gate is AND/OR, next at the step 27, the level of a new object to be generated is set to be the level of the current object. On the other hand, when the driving logic gate is NAND/NOR, next at the step 28, the level of a new object to be generated is set to be an opposite value of the level of the current object.
The object can be propagated up to the primary input by executing the operation of the steps 21 to 28 for each object sequentially.
As a concrete illustrative example, for an exemplary circuit shown in FIG. 3, the test pattern generation according to the conventional method of [Ref. 1] proceeds as follows. Here, in the circuit of FIG. 3, the stuck at 0 fault is assumed to be present at the signal line I.
In this case, according to the conventional method of [Ref. 1], the object (I, 1) for setting the level 1 to the signal line I with the fault is generated first. Then, as the driving logic gate of this signal line I is NAND, the next object (B, 0) is generated according to the flow chart of FIG. 2. Also, the signal line B is the primary input, so that the logic value 0 is assigned to this primary input at B. As a result, at the signal line I, the logic value is 1 in a case of the absence of the fault or 0 in a case of the presence of the fault, so that the fault signal can be generated.
Next, in order to observe this fault signal at the primary output, it is necessary to activate the path which is connected to the primary output. For example, in a case of observing the fault signal through a signal line K. In this case, the object (H, 1) is generated first, and as the driving logic gate of the signal line H is OR, the objects (E, 1), (N, 0), and (O, 1) are subsequently generated sequentially. Then, as the signal line O is the primary input, the logic value 1 is assigned to this primary input at 0.
At this point, however, as the fault signal has not passed through the signal line K yet, so that the object (H, 1) is generated again. Then, similarly as above, the objects (E, 1) and (N, 0) are generated subsequently. In this case, the primary input at 0 has already assigned the logic value 1, so that the object generated from the object (N, 0) is going to (A, 1). Then, as the signal line A is the primary input, the logic value 1 is assigned to this primary input at A. As a consequence, a signal line N is going to have the logic value 0, a signal line E is going to have the logic value 1, a signal line H is going to have the logic value 1, a signal line F is going to have the logic value 0, a signal line G is going to have the logic value 0, a signal line J is going to have the logic value 0, and a signal line M is going to have the logic value 0.
In this case, the fault signal has reached to the signal line K, but the primary output M is going to have the logic value 0, so that the fault signal cannot be observed at the primary output. In order to resolve this conflict, according to [Ref. 1], the assignments of the logic values are carried out anew by the backtracking operation. Here, the last assignment of the logic value made was the setting of the level 1 to the signal line A, so that the level 0 is re-assigned to the signal line A by the backtracking. As a consequence, a signal line N is going to have the logic value 1, a signal line E is going to have the logic value 0, a signal line F is going to have the logic value 0, a signal line G is going to have the logic value 0, a signal line H is going to have the logic value 0, a signal line K is going to have the logic value 0, and a signal line M is going to have the logic value 0. Thus, the conflict is still not resolved, so that the further backtracking is necessary.
Thus, next, the signal line A is set back to the variable value, and the setting of the logic value 0 to the signal line O is tried. The result of this try is again that the conflict is still not resolved, so that the further backtracking is necessary.
Thus, next, the signal line O is set back to the variable value, and the setting of the logic value 1 to the signal line B is tried. The result of this try is that the conflict is resolved, but the signal line I is going to have the variable value, so that the object (I, 1) for producing the fault signal is generated again. In this case, as the signal line B has the logic value 1, the object (C, 0) is generated from the object (I, 1), and as the signal line C is the primary input, the logic value 0 is assigned to this primary input at C. As a result, the fault signal reaches to the signal line K, so that in order to observe this fault signal at the primary output M, the object (J, 1) is generated next. Hereafter, in the procedure similar to that described above, the logic value 1 is assigned to the primary input at 0 and the primary input at A, and it becomes possible to observe the fault signal at the primary output M.
According to [Ref. 1], this procedure is repeated until either the fault signal reaches to the primary output, or all the primary input logic value settings are exhausted.
In such a conventional test pattern generation method, however, as a number of backtracking operations increases, the re-assignments of the logic values are going to be repeated many times, so that the speed of the test pattern generation become slower.
Thus, in order to carry out the test pattern generation efficiently, it is necessary to reduce the number of backtracking operations. However, in the conventional test pattern generation method, there are cases in which many assignments of the logic values are required until the conflict can be found, and in such cases, the backtracking operations are going to be carried out for these many assigned logic values, so that an enormous amount time can be required for resolving the conflict, and consequently the efficiency of the test pattern generation can be lowered significantly.
Therefore, the early discovery and the early resolution of the conflict have a crucially importance to the speeding up of the test pattern generation.